package com.huawei.od;

import java.util.*;

/**
 * 239. 滑动窗口最大值
 */
public class TestFour {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) {
            return new int[0];
        }
        Deque<Integer> win = new LinkedList<>();
        int count = 0;
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            if (i >= k && win.peekLast() <= i - k) {
                win.pollLast();
            }
            while (!win.isEmpty() && nums[win.peekFirst()] <= nums[i]) {
                win.pollFirst();
            }
            win.offerFirst(i);
            if (i >= k - 1) {
                res[count++] = nums[win.peekLast()];
            }
        }
        return res;
    }
}
